/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
  const x = board[0].length;
  const y = board.length;
  const visited: Map<number, boolean[]> = new Map();
  for (let i = 0; i < y; i++) {
    for (let j = 0; j < x; j++) {
      if ((i === 0 || i === y - 1 || j === 0 || j === x - 1) && board[i][j] === 'O') dfs(i, j);
    }
  }
  for (let i = 0; i < y; i++) {
    for (let j = 0; j < x; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      if (board[i][j] === 'N') board[i][j] = 'O';
    }
  }
  function dfs(i: number, j: number) {
    const dx = [-1, 0, 0, 1];
    const dy = [0, -1, 1, 0];
    board[i][j] = 'N';
    if (!visited?.[i]?.length) visited[i] = [];
    visited[i][j] = true;
    for (let d = 0; d < 4; d++) {
      const nx = j + dx[d];
      const ny = i + dy[d];
      if (nx < 0 || nx >= x || ny < 0 || ny >= y) continue;
      if (board[ny][nx] !== 'O') continue;
      if (visited?.[ny]?.[nx]) continue;
      dfs(ny, nx);
    }
  }
};